package com.example.zz.example.datastructures.nowcoder;

import java.util.HashMap;

/**
 * @author: zhuozhang6
 * @date: 2021/12/1
 * @email: zhuozhang6@iflytek.com
 * @Description: 查找算法
 */
public class SearchOffer {
    public static void main(String[] args) {

        //数组中查找两数之和为target的两数角标
        twoSumProblem();
    }

    private static void twoSumProblem() {
        int[] nums = new int[]{1, 2, 7, 11, 15};
        int[] ints = twoSum(nums, 9);
        int[] ints2 = twoSum2(nums, 9);
        System.out.println("ints = " + ints[0] + " " + ints[1]);
        System.out.println("ints2 = " + ints2[0] + " " + ints2[1]);
    }

    //{1, 2, 7, 11, 15}
    //使用hashmap的containsKey方式判断
    public static int[] twoSum(int[] nums, int target) {
        int[] ret = new int[2];
        HashMap<Integer, Integer> hashMap = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            int temp = target - nums[i];
            if (hashMap.containsKey(temp)) {
                ret[0] = hashMap.get(temp);
                ret[1] = i;
            }
            hashMap.put(nums[i], i);
        }
        return ret;
    }

    //暴力循环法
    public static int[] twoSum2(int[] nums, int target) {
        int[] ret = new int[2];
        for (int i = 0; i < nums.length; i++) {
            for (int j = i + 1; j < nums.length; j++) {
                if (nums[i] + nums[j] == target) {
                    ret[0] = i;
                    ret[1] = j;
                }
            }
        }
        return ret;
    }
}
